package com.tgy.heap;


import com.tgy.util.printer.BinaryTreeInfo;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;

/**
 * 最大堆
 * @Author: tgy
 * @Date: 2020-10-10 10:28
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<E> implements Heap<E>, BinaryTreeInfo {

    private int size;

    private E[] container;

    private Comparator<E> comparator;

    private static final int INIT_CAPACITY = 10;

    public BinaryHeap() {

        this(null,null);
    }

    public BinaryHeap(Comparator<E> comparator) {

       this(comparator,null);
    }

    public BinaryHeap(Comparator<E> comparator, E[] elements) {

        this.comparator = comparator;

        if (Objects.isNull(elements) || elements.length == 0) {

            container = (E[]) new Object[INIT_CAPACITY];
        }else {

            container = (E[]) new Object[elements.length];
            size = elements.length;

            for (int i = 0; i < elements.length; i++) {

                container[i] = elements[i];
            }

            heapify();
        }

    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {

        for (int i = 0; i < size; i++) {

            container[i] = null;
        }

        size = 0;
    }

    @Override
    public void add(E element) {

        checkElement(element);
        /**
         * 扩容
         */
        ensureContainer();

        container[size++] = element;

        /**
         * 调整添加的元素
         */
        siftUp(size - 1);
    }

    @Override
    public E get() {

        checkIndex(0);
        return container[0];
    }

    @Override
    public E remove() {

        checkIndex(0);

        E e = container[0];

        container[0] = container[--size];

        // 删除最后一个元素
        container[size] = null;

        // 删除元素后数组里面的元素大于1才进行下滤
        if (size > 1) {

            siftDown(0);
        }

        return e;
    }

    @Override
    public E replace(E element) {

        checkElement(element);

        if (isEmpty()) {

            container[0] = element;
            size++;
            return null;
        }

        E e = container[0];

        container[0] = element;

        if (size > 1) {

            siftDown(0);
        }
        return e;
    }

    @Override
    public void tranversal(Visitor<E> visitor) {

        for (int i = 0; i < size; i++) {

            if (visitor.visit(container[i])) {
                break;
            }
        }

    }


    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {


        int leftIndex = (((int) node) << 1) + 1;
        return leftIndex < size ? leftIndex: null;
    }

    @Override
    public Object right(Object node) {

        int rightIndex = (((int) node) << 1) + 2;
        return rightIndex < size ? rightIndex: null;
    }

    @Override
    public Object string(Object node) {

        return container[(int) node];
    }

    /**
     * 构建堆,使用 自下往上的下滤
     */
    private void heapify() {

        if (size == 1) {

            return;
        }
//       非叶子节点个数 size >> 1
        for (int i = (size >> 1) - 1; i >= 0 ; i--) {

            siftDown(i);
        }

    }


    /**
     * 上滤index节点的元素
     * @param index
     */
    private void siftUp(int index) {

        checkIndex(index);

        E e = container[index];

        int pIndex;

        while (index > 0) {

            pIndex = (index - 1) >> 1;

            if (compare(e,container[pIndex]) <= 0) {

                break;
            }

            container[index] = container[pIndex];

            index = pIndex;
        }

        container[index] = e;
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {

        checkIndex(index);

        E e = container[index];

        int maxIndex = 0;
        // 非叶子节点，进入循环
        while (index < (size >> 1)) {

            int leftIndex = (index << 1) + 1;
            E maxElement = container[leftIndex];

            maxIndex = leftIndex;
            if (leftIndex + 1 < size && this.compare(maxElement,container[leftIndex + 1]) < 0) {

                maxElement = container[leftIndex + 1];
                maxIndex = leftIndex + 1;
            }

            if (this.compare(e,maxElement) > 0) {

                break;
            }

            container[index] = container[maxIndex];
            index = maxIndex;
        }

        container[index] = e;
    }

    /**
     * 比较两个元素
     * @param e1 mm
     * @param e2
     * @return
     */
    private int compare(E e1,E e2) {

        if (Objects.nonNull(comparator)) {

            return comparator.compare(e1,e2);
        }

        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 扩容
     */
    private void ensureContainer() {

        if (size < container.length) {

            return;
        }

        int newLength = container.length + (container.length >> 1);

        E[] newContainer = (E[]) new Object[newLength];

        for (int i = 0; i < size; i++) {

            newContainer[i] = container[i];
        }

        container = newContainer;
    }

    /**
     * 检查元素是否为null
     * @param element
     */
    private void checkElement(E element) {

        if (Objects.isNull(element)) {

            throw new IllegalArgumentException("add element not null");
        }
    }

    private void checkIndex(int index) {

        if (index >= container.length || index < 0) {

            throw new IndexOutOfBoundsException("index out of bounds");
        }
    }

}
